Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

  1. /**
  2.  * Definition for an interval.
  3.  * public class Interval {
  4.  *     int start;
  5.  *     int end;
  6.  *     Interval() { start = 0; end = 0; }
  7.  *     Interval(int s, int e) { start = s; end = e; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<Interval> merge(List<Interval> intervals) {
  12.     // sort
  13.     Collections.sort(intervals, new Comparator<Interval>() {
  14.       public int compare(Interval a, Interval b) {
  15.         return a.start - b.start;
  16.       }
  17.     });
  19.     // merge
  20.     Stack<Interval> stack = new Stack<Interval>();
  22.     for (int i = 0; i < intervals.size(); i++) {
  23.       Interval curr = intervals.get(i);
  25.       if (stack.isEmpty() || curr.start > stack.peek().end) {
  26.         stack.push(curr);
  27.       } else {
  28.         stack.peek().end = Math.max(curr.end, stack.peek().end);
  29.       }
  30.     }
  32.     // return
  33.     List<Interval> res = new ArrayList<Interval>();
  34.     while (!stack.isEmpty()) {
  35.       res.add(stack.pop());
  36.     }
  38.     return res;
  39.   }
  40. }